import java.util.Arrays;

/**
 * 给出基数为 -2的两个数arr1 和arr2，返回两数相加的结果。
 * 数字以数组形式给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr= [1,1,0,1]表示数字(-2)^3+ (-2)^2 + (-2)^0 = -3。数组形式的数字也同样不含前导零：以 arr 为例，这意味着要么arr == [0]，要么arr[0] == 1。
 * 返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。
 * <p>
 * 示例：
 * 输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]
 * 输出：[1,0,0,0,0]
 * 解释：arr1 表示 11，arr2 表示 5，输出表示 16 。
 * <p>
 * 提示：
 * 1 <= arr1.length <= 1000
 * 1 <= arr2.length <= 1000
 * arr1 和arr2都不含前导零
 * arr1[i] 为0或1
 * arr2[i] 为0或1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/adding-two-negabinary-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * 参考了别人的答案
 */
public class Q01073m_Ans {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int[] ans = new int[Math.max(arr1.length, arr2.length) + 3];
        int i = arr1.length - 1, j = arr2.length - 1, idx = ans.length - 1, jw = 0;
        while (i >= 0 || j >= 0 || jw != 0) {
            if (i >= 0) {
                jw += arr1[i];
                i--;
            }
            if (j >= 0) {
                jw += arr2[j];
                j--;
            }
            ans[idx] = Math.abs(jw) % 2;
            if (jw == -1) { // 前一位为正，向前进1
                jw = 1;
            } else if (jw >= 2) { // 向前进-1
                jw = -1;
            } else { // 不进位
                jw = 0;
            }
            idx--;
        }
        while (idx < ans.length - 1 && ans[idx] == 0) { // 去除前导0
            idx++;
        }
        return idx == 0 ? ans : Arrays.copyOfRange(ans, idx, ans.length);
    }
}
